
/*
 *  Copyright t lefering
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  These are the four essential freedoms with GNU GPL software:
 *  1: freedom to run the program, for any purpose
 *  2: freedom to study how the program works, and change it to make it do what you wish
 *  3: freedom to redistribute copies to help your Free Software friends
 *  4: freedom to distribute copies of your modified versions to your Free Software friends
 *   ,           ,
 *  /             \
 * ((__-^^-,-^^-__))
 * `-_---'  `---_-'
 *  `--|o`   'o|--'
 *      \  `  /
 *       ): :(
 *       :o_o:
 *        "-"
 */

/*
 * The ISI layout algorithm is to produce a linear time (quick) layout.
 * It does a depth first search in each direction (X, Y) placing nodes as follows:
 * - leaf nodes are placed a fixed distance from any previously layed out leaf node
 * - other nodes are layed out at the average position of their children
 *     (which causes them to sometimes overlap)
 * Gabriel Robins (at Information Sciences Institute, Marina Del Rey, CA)
 * "The ISI Grapher: a Portable Tool for Displaying Graphs Pictorially"
 * Symboliikka '87 Helsinki, Finland August 17-18, 1987
 */

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>

#include "main.h"

static int globallastx = 0;

static struct isi_nlist *findtopnodes (struct isi_graph *g);
static struct isi_nlist *findbottomnodes (struct isi_graph *g);
static void isilayoutx (struct isi_graph *g, struct isi_node *n);
static int isixavekidsofnode (struct isi_graph *g, struct isi_node *n);
static void isilayouty (struct isi_graph *g, struct isi_node *n);
static struct isi_nlist *findkidsofnode (struct isi_node *n);
static struct isi_nlist *findparentsofnode (struct isi_node *n);
static int isiymaxparents (struct isi_graph *g, struct isi_node *n);


/* run layout */
void
isilayout (struct isi_graph *g)
{
  struct isi_nlist *p;

  /* offset of drawing */
  globallastx = g->xbase;

  /* mark all nodes undisplayed */
  p = g->headnode;

  while (p)
    {
      p->node->displayed = 0;
      p = p->next;
    }

  /* list with nodes with no incoming edges */
  p = findtopnodes (g);

  while (p)
    {
      isilayoutx (g, p->node);
      p = p->next;
    }

  /* mark all nodes undisplayed */
  p = g->headnode;

  while (p)
    {
      p->node->displayed = 0;
      p = p->next;
    }

  /* list with nodes with no outgoing edges */
  p = findbottomnodes (g);

  while (p)
    {
      isilayouty (g, p->node);
      p = p->next;
    }

  return;
}

/* nodes with no incoming edges */
static struct isi_nlist *
findtopnodes (struct isi_graph *g)
{
  struct isi_nlist *p;
  struct isi_nlist *q;
  struct isi_nlist *newl;
  struct isi_nlist *newltail;

  newl = NULL;
  newltail = NULL;

  p = g->headnode;

  while (p)
    {
      /* no incoming edges to node at a toplevel node */
      if (p->node->countpred == 0)
	{
	  /* append */
	  q = calloc (1, sizeof (struct isi_nlist));
	  q->node = p->node;

	  if (newl == NULL)
	    {
	      newl = q;
	    }
	  else
	    {
	      newltail->next = q;
	    }
	  newltail = q;
	}
      p = p->next;
    }

  p = newl;

  printf ("head nodes:");

  while (p)
    {
      printf ("%d ", p->node->number);
      p = p->next;
    }
  printf ("\n");

  return (newl);
}

/* nodes with no outgoing edges */
static struct isi_nlist *
findbottomnodes (struct isi_graph *g)
{
  struct isi_nlist *p;
  struct isi_nlist *q;
  struct isi_nlist *newl;
  struct isi_nlist *newltail;

  newl = NULL;

  p = g->headnode;

  while (p)
    {
      /* no outgoing edges from node in list appended */
      if (p->node->countsucc == 0)
	{
	  /* append */
	  q = calloc (1, sizeof (struct isi_nlist));
	  q->node = p->node;
	  if (newl == NULL)
	    {
	      newl = q;
	    }
	  else
	    {
	      newltail->next = q;
	    }
	  newltail = q;
	}
      p = p->next;
    }

  return (newl);
}

/* */
static void
isilayoutx (struct isi_graph *g, struct isi_node *n)
{
  int flag;
  struct isi_nlist *kidslist;
  struct isi_nlist *p;

  /* check if aready done */
  if (n->displayed)
    {
      return;
    }

  /* scan for unlayouted kids */
  flag = 0;

  kidslist = findkidsofnode (n);

  p = kidslist;

  while (p)
    {
      /* check if displayed */
      if (p->node->displayed == 0)
	{
	  /* node is not layouted yet */
	  flag = 1;
	  break;
	}
      p = p->next;
    }

  if (flag == 0)
    {
      /* all kids layouted */
      n->x = globallastx + g->xspace;
      globallastx = n->x + n->width;
    }
  else
    {
      /* kids to layout */
      p = kidslist;

      while (p)
	{
	  if (p->node->displayed == 0)
	    {
	      /* do layout of kid */
	      isilayoutx (g, p->node);
	    }
	  p = p->next;
	}
      n->x = isixavekidsofnode (g, n);
    }

  /* mark node is ready */
  n->displayed = 1;

  return;
}


/* */
static int
isixavekidsofnode (struct isi_graph *g, struct isi_node *n)
{
  struct isi_nlist *p;
  int avg;
  int count;

  /* get outgoing edges */
  p = findkidsofnode (n);

  count = 0;
  avg = 0;

  while (p)
    {
      count++;
      avg = avg + p->node->x;
      p = p->next;
    }

  if (count)
    {
      return (avg / count);
    }
  else
    {
      return (0);
    }
}


/* */
static void
isilayouty (struct isi_graph *g, struct isi_node *n)
{
  struct isi_nlist *parentlist;


  /* check if aready done */
  if (n->displayed)
    {
      return;
    }

  /* outgoing edges */
  parentlist = findparentsofnode (n);

  if (n->countpred)
    {

      while (parentlist)
	{
	  isilayouty (g, parentlist->node);
	  parentlist = parentlist->next;
	}
      n->y = (isiymaxparents (g, n) + g->yspace);
    }
  else
    {
      /* no outgoing edges */
      n->y = g->ybase;
    }

  /* mark node is ready */
  n->displayed = 1;

  return;
}


static int
isiymaxparents (struct isi_graph *g, struct isi_node *n)
{
  int max;
  struct isi_nlist *parentlist;

  if (g)
    {
    }

  max = 0;

  /* outgoing edges */
  parentlist = findparentsofnode (n);

  while (parentlist)
    {
      if (parentlist->node->y + parentlist->node->height > max)
	{
	  max = parentlist->node->y + parentlist->node->height;
	}
      parentlist = parentlist->next;
    }
  return max;
}

/* */
static struct isi_nlist *
findkidsofnode (struct isi_node *n)
{
  /* list of the nodes in outgoing edges */
  return (n->succlist);
}

static struct isi_nlist *
findparentsofnode (struct isi_node *n)
{
  /* list of the nodes in incoming edges */
  return (n->predlist);
}

/* end */
